package com.company.笔试.矩阵dfs;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author 11
 * @Date 2021/6/27 10:33
 * @Version 1.0
 */


import java.util.*;


public class Solution {
    /**
     * return the shortest path
     * @param matrix string字符串一维数组 the matrix
     * @return int整型
     */

    public static int len;
    public static int wid;
    public static int index=0;
    public static int res;
    public static int realRes;
    public static int[] xarr={0,1,0,-1};
    public static int[] yarr={1,0,-1,0};
    public static boolean[][] flag;
    public int shortestPath (String[] matrix) {
        // write code here
        if(matrix !=null && matrix.length>0 && matrix[0].charAt(0)=='0') return res;
        len = matrix.length-1;
        wid = matrix[0].length()-1;
        flag = new boolean[len+wid][wid+len];
        System.out.println(len+"  len   wid"+wid);
//        flag[0][0]=true;
        res=1;
        dfs(matrix,0,0);
        return realRes;
    }
    public void dfs(String[] matrix,int x,int y){
        if(x>wid||x<0||y>len||y<0)return;
//        System.out.println(x+"  "+y+"falg"+flag[x][y]);
        if (flag[x][y]) {
//            System.out.println("falg"+flag[x][y]);
            return;
        }
        if(matrix[y].charAt(x)=='0') return;
        if (x==wid&&y==len){
//            System.out.println("结束！");
//            System.out.println(res);
            realRes = res;
            return;
        }
        res++;
        flag[x][y]=true;
        int xx,yy;
        for(int i=0;i<4;i++){
            xx=x+xarr[i];// x    x+1   x
            yy=y+yarr[i];// y+1  y     y-1
//            System.out.println(index++ + " "+xx+"  "+yy);
//            if (xx==4){
//                System.out.println(xx);
//            }
            dfs(matrix,xx,yy);
//            flag[xx][yy]=false;
        }

//        flag[x][y]=true;
//        dfs(matrix,x,y+1);
//        dfs(matrix,x+1,y);
//        dfs(matrix,x,y-1);
//        dfs(matrix,x-1,y);
    }

    public static void main(String[] args) {
        String[] arr = {"10111","10101","11111","00001"};
        System.out.println(new Solution().shortestPath(arr));
    }
}